<?php
# @version SVN: $Id: tree.class.inc 576 2012-03-24 17:39:01Z novachok $

class tree
{
   static public $isBuilded = FALSE;

   private $_tree  = NULL;
   private $_nodes = NULL;

   public function  __construct()
   {
      $DB = database::getInstance();
      $DB->sql = 'SELECT `t`.*, `t_tr`.*
         FROM `meccano_tree` AS `t`, `meccano_tree_translate` AS `t_tr`
         WHERE `t`.`id` = `t_tr`.`id`
         ORDER BY `t`.`lt` ASC, `t_tr`.`lang` ASC';
      $fetched = $DB->DB_Fetch();
      if($fetched == FALSE) return FALSE;

      # REBUILD ACCORDING WITH LANGS
      $tmp = array();
      for($i=0, $t=count($fetched); $i<$t; $i++)
      {
         $tmp[$fetched[$i]['id']][$fetched[$i]['lang']] = $fetched[$i];
      }
      $fetched = $tmp;
      unset($tmp);

      $this->_tree = $this->buildTree($fetched);
      tree::$isBuilded = TRUE;
   }


   /**
    * Get Instance of TREE object
    *
    * @staticvar object $object_store_singelton
    * @return object
    */
   static public function getInstance()
   {
      static $object_store_singelton;
      if(!is_object($object_store_singelton))
      {
         $object_store_singelton = new tree();
      }
      return $object_store_singelton;
   }


   /**
    * Build Tree and Nodes from SQL fetched into array data
    *
    * @param array $list
    * @param object $parent
    * @return array
    */
   private function buildTree(&$list, $parent = NULL)
   {
      $branch = array();
      $node   = NULL;

      while(!empty($list))
      {
         $node_input_inner = reset($list);
         $node_input_inner = reset($node_input_inner);
         if(!empty($node) && $node->level < $node_input_inner['level'])
         {
            $node->childs = $this->buildTree($list, $node->id);
         }

         if(empty($list)) continue;
         $node_input_inner = reset($list);
         $node_input_inner = reset($node_input_inner);
         if(!empty($node) && $node->level > $node_input_inner['level'])
         {
            break;
         }

         $node = new category(array_shift($list));
         if(!empty($parent))
         {
            $node->parent = $parent;
         }

         $branch[$node->id] = $node;
         $this->_nodes[$node->id] = $node;
      }

      return $branch;
   }



   /**
    * Get Node object
    *
    * @param mixed $id - id or alias of the node
    * @param integer $force_parent - force node to be child of the given Parent ID
    * @return object
    */
   public function getNode($id, $force_parent = NULL)
   {
      if(!empty($this->_nodes[$id]))
      {
         # Get Node by ID
         return $this->_nodes[$id];

      } elseif(!is_numeric($id))
      {
         # Get Node by Alias
         foreach($this->_nodes AS $node)
         {
            if($node->alias == $id && ($force_parent === NULL || $node->parent == $force_parent))
            {
               return $node;
            }
         }
      }

      return FALSE;
   }


   /**
    * Create empty Node - for saving new one
    *
    * @param integer $parent_id - parent node id
    * @return object
    */
   public function getEmptyNode($parent_id)
   {
      if(is_numeric($parent_id))
      {
         return new category($parent_id);
      }

      return NULL;
   }


   /**
    * Get flatted tree
    *
    * @return array
    */
   public function getFlatTree()
   {
      return $this->_nodes;
   }


   /**
    * Get Tree hierarchy from gimen point or from root
    *
    * @param integer $id
    * @return object
    */
   public function getTree($id = 0)
   {
      if(empty($id))
      {
         return $this->_tree;
      } elseif(!empty($this->_nodes[$id]))
      {
         return $this->_nodes[$id];
      }

      return FALSE;
   }


   /**
    * @param integer $id - id of node
    * @param string $mode output mode: array|string (coma separated string)
    */
   public function getPathId($id, $mode = 'array')
   {
      if(empty($this->_nodes[$id]))
         return FALSE;

      $path = $this->getPath($id);
      $output = array();
      if(!empty($path))
      {
         foreach($path AS $node)
         {
            $output[] = $node->id;
         }
      }

      if($mode == 'string')
      {
         $output = implode(',', $output);
      }

      return $output;
   }


   /**
    * Get IDs from all childs of NODE as deep as it is
    *
    * @param integer $id
    * @param string $mode
    * @param boolean $clear
    * @return mixed
    */
   public function getChildrenId($id, $mode='array', $clear=TRUE)
   {
      $output = array();

      if(empty($this->_nodes[$id])) return FALSE;

      if(sizeof($this->_nodes[$id]->childs) == 0 ||
         ($clear == TRUE &&
            ($this->_nodes[$id]->system == 1 ||
               $this->_nodes[$id]->active != 1 ||
               in_array('hidden', $this->_nodes[$id]->types))))
         return FALSE;

      foreach($this->_nodes[$id]->childs AS $child)
      {
         $output[] = $child->id;
         $tmp = $this->getChildrenId($child->id, 'array', $clear);
         if(!empty($tmp)) $output = array_merge($output, $tmp);
      }


      if($mode == 'string') $output = implode(',', $output);
      return $output;
   }


   public function getPath($id)
   {
      $path = array();
      while(!empty($id))
      {
         array_unshift($path, $this->_nodes[$id]);
         $id = $this->_nodes[$id]->parent;
      }

      return $path;
   }


   /**
    * Create new node from given data
    *
    * @param integer $parent_id - parent node id
    * @param array $data
    * @return object
    */
   public function addNode($parent_id, $data)
   {
      $parent = $this->getNode($parent_id);
      $DB = database::getInstance();
      if($parent)
      {
         $right = $parent->rt;
         $level = $parent->level + 1;
      } else
      {
         $right = $DB->DB_GetNextID('rt', 'meccano_tree');
         $level = 1;
      }

      $DB->sql = 'UPDATE `meccano_tree` SET `rt` = `rt` + 2,  `lt` = IF(`lt` >= '. $right .', `lt` + 2, `lt`) WHERE `rt` >= '. $right;
      $DB->DB_Query();

      $node = new category($parent_id);
      $node->lt    = $right;
      $node->rt    = $right + 1;
      $node->level = $level;

      $newnode = $node->save($data);
      if(!$newnode)
      {
         # ROLLBACK IF FAILE
         $right += 2;
         $DB->sql = 'UPDATE `meccano_tree` SET `rt` = `rt` - 2,  `lt` = IF(`lt` >= '. $right .', `lt` - 2, `lt`) WHERE `rt` >= '. $right;
         $DB->DB_Query();
      } else
      {
         $this->updateNodesPositions($newnode->rt);
      }

      return $newnode;
   }


   /**
    * Move node
    *
    * @param integer $id
    * @param array $positions - array('parent'=>integer, 'after'=>integer, 'before'=>integer, 'last'=>bool)
    */
   public function moveNode($id, $positions = array())
   {
      $e = FALSE;
      if(empty($this->_nodes[$id])) return FALSE;

      # Check Parent node
      if(empty($positions['parent']))
      {
         $positions['parent'] = 0;
      } else
      {
         $positions['parent'] = $this->_nodes[$positions['parent']];
      }


      $newLeftPosition  = NULL;
      $newLevelPosition = NULL;
      # Get Left point for new position
      if(empty($positions['last']) && !empty($positions['parent']) && !empty($positions['after']) && $positions['parent']->id == $positions['after'])
      {
         //echo "1: Parent: ". $positions['parent']->id .", After: ". $positions['after'] ."\n";
         # If we place node just after parent in left side
         $newLeftPosition  = $positions['parent']->lt + 1;
         $newLevelPosition = $positions['parent']->level + 1;
      } elseif(empty($positions['last']) && !empty($positions['after']) && !empty($this->_nodes[$positions['after']]))
      {
         //echo "2\n";
         # If we place node between other nodes and there are given a node after which
         $newLeftPosition  = $this->_nodes[$positions['after']]->rt + 1;
         $newLevelPosition = $this->_nodes[$positions['after']]->level;
      } elseif(empty($positions['last']) && !empty($positions['before']) && !empty($this->_nodes[$positions['before']]))
      {
         //echo "3\n";
         # IF we place a node between other nodes and there are given a node before which
         if(empty($this->_nodes[$positions['before']]->parent))
         {
            $rangNodes = $this->_tree;
         } else
         {
            $tmp = $this->_nodes[$this->_nodes[$positions['before']]->parent];
            $rangNodes = $tmp->childs;
         }
         $beforeNode = NULL;
         foreach($rangNodes AS $node)
         {
            if($node->id == $this->_nodes[$positions['before']]->id)
            {
               break;
            }
            $beforeNode = $this->_nodes[$positions['before']];
         }
         if(!empty($beforeNode))
         {
            $newLeftPosition  = $beforeNode->lt;
            $newLevelPosition = $beforeNode->level;
         }
      }

      if(empty($newLeftPosition) && empty($newLevelPosition))
      {
         if(!empty($positions['parent']) && !empty($positions['parent']->childs))
         {
            //echo "4\n";
            # If we place node in right side under parent
            $LastChild = end($positions['parent']->childs);
            $newLeftPosition  = $LastChild->rt + 1;
            $newLevelPosition = $LastChild->level = $LastChild->level;
         } else
         {
            //echo "5\n";
            $LastChild = end($this->_tree);
            $newLeftPosition  = $LastChild->rt + 1;
            $newLevelPosition = 1;
         }
      }


      # Reorder nodes
      $sql = array();
      $NodeDeltaPosition = $this->_nodes[$id]->rt - $this->_nodes[$id]->lt + 1;
      $NodeDeltaShift    = $newLeftPosition - $this->_nodes[$id]->lt;

      $sql[] = 'UPDATE `meccano_tree` SET `lt` = -lt, `rt` = -rt
         WHERE `lt` >= '. $this->_nodes[$id]->lt .' AND `rt` <= '. $this->_nodes[$id]->rt;
      $sql[] = 'UPDATE `meccano_tree` SET `lt` = IF(`lt` > '. $this->_nodes[$id]->lt .', `lt` -' . $NodeDeltaPosition . ', `lt`),
         `rt` = IF(`rt` > '. $this->_nodes[$id]->rt .', `rt` -' . $NodeDeltaPosition . ', `rt`)
         WHERE `rt` > '. $this->_nodes[$id]->rt;
      $sql[] = 'UPDATE `meccano_tree` SET `lt` = `lt` + '. $NodeDeltaPosition .' WHERE `lt` >= '.
         ($newLeftPosition > $this->_nodes[$id]->lt ? $newLeftPosition - $NodeDeltaPosition : $newLeftPosition); // сдвигает на 1 больше
      $sql[] = 'UPDATE `meccano_tree` SET `rt` = `rt` + '. $NodeDeltaPosition .' WHERE `rt` >= '.
         ($newLeftPosition > $this->_nodes[$id]->lt ? $newLeftPosition - $NodeDeltaPosition : $newLeftPosition); // сдвигает на 1 больше
      $sql[] = 'UPDATE `meccano_tree` SET `lt` = ABS(`lt`) + '. $NodeDeltaShift .', `rt` = ABS(`rt`) + '.  $NodeDeltaShift
         .', `level` = (`level` + '. $newLevelPosition .' - '. $this->_nodes[$id]->level .')
         WHERE `lt` < 0';

      $DB = database::getInstance();
      $DB->DB_StartTransaction();
      foreach($sql AS $query)
      {
         //echo $query ."\n";
         $DB->sql = $query;
         $DB->DB_Query();
      }
      $e = $DB->DB_EndTransaction();

      return $e;
   }


   public function deleteNode($id, $child = FALSE)
   {
      $node = $this->getNode($id);
      if($node)
      {
         $e = FALSE;
         if($child == FALSE)
         {
            $DB = database::getInstance();
            $DB->DB_StartTransaction();
            $DB->sql = 'DELETE `t1`.*, `t2`.* FROM `meccano_tree` AS `t1`, `meccano_tree_translate` AS `t2`
               WHERE `t1`.`lt` >= ' . $node->lt . ' 
               AND `t1`.`rt` <= ' . $node->rt . '
               AND `t1`.`id` = `t2`.`id`';
            $DB->DB_Query();
            $DB->sql = 'UPDATE `meccano_tree`
               SET `lt` = IF(`lt` > ' . $node->lt . ', `lt` - (' . $node->rt . ' - ' . $node->lt . ' + 1), `lt`),
               `rt` = `rt` - (' . $node->rt . ' - ' . $node->lt . ' + 1)
               WHERE `rt` > ' . $node->rt;
            $DB->DB_Query();
            $e = $DB->DB_EndTransaction();
         }

         if($e || $child)
         {
            $node->delete();
            if(!empty($node->childs))
            {
               foreach($node->childs AS $n)
               {
                  $this->deleteNode($n->id, TRUE);
               }
            }
            unset($this->_nodes[$node->id]);
         }

         if($e && $child == FALSE)
         {
            $this->updateNodesPositions();
         }

         return $e;
      }
   }


   /**
    * Update Tree's LEFT, RIGHT positions
    *
    * @param integer $rt
    */
   private function updateNodesPositions($rt = NULL)
   {
      $DB = database::getInstance();

      $sql = 'SELECT id, rt, lt FROM meccano_tree';
      if(!empty($rt) && is_numeric($rt)) $sql .= ' WHERE lt > '. $rt;
      $DB->sql = $sql;
      $rows = $DB->DB_FetchFlat();

      for($i=0, $t=count($rows); $i<$t; $i++)
      {
         if(!empty($this->_nodes[$rows[$i]['id']]))
         {
            $this->_nodes[$rows[$i]['id']]->lt = $rows[$i]['lt'];
            $this->_nodes[$rows[$i]['id']]->rt = $rows[$i]['rt'];
         }
      }
   }
}



class tree_static
{
   static private $prebuildedTree = array();

   static public function getNode($id)
   {
      $TREE = tree::getInstance();
      return $TREE->getNode($id);
   }

   static public function getPath($id)
   {
      $TREE = tree::getInstance();
      return $TREE->getPath($id);
   }

   /**
    * GET IDs of NODE's childs deep as they are
    *
    * @param integer $id
    * @param string $mode
    * @param boolean $clear
    * @return mixed
    */
   static public function getChildrenId($id, $mode='array', $clear=TRUE)
   {
      $TREE = tree::getInstance();
      return $TREE->getChildrenId($id, $mode='array', $clear=TRUE);
   }

   static public function prebuildPathId($node)
   {
      if(tree::$isBuilded)
      {
         $TREE = tree::getInstance();
         return $TREE->getPathId($node);
      } else
      {
         if(empty(self::$prebuildedTree))
         {
            self::prebuildTree();
         }

         if(is_numeric($node) && !empty(self::$prebuildedTree[$node]))
         {
            $ids = array($node);
            if(!empty(self::$prebuildedTree[$node]['path']))
            {
               foreach(self::$prebuildedTree[$node]['path'] AS $n)
               {
                  $ids[] = $n['id'];
               }
            }
            return $ids;
         }
      }
   }

   static private function prebuildTree()
   {
      $DB      = database::getInstance();
      $DB->sql = 'SELECT `id`, `level` FROM `meccano_tree` ORDER BY `lt` ASC';
      $fetched = $DB->DB_Fetch();


      $tree     = array(); # HIERARCHY ARRAY
      $chain[1] = &$tree;  # BUILDING HIERARCHY
      $level    = 1;       # HIERARCHY LEVEL

      for($i=0, $t=count($fetched); $i<$t; $i++)
      {
         $f['id']    = $fetched[$i]['id'];
         $f['level'] = $fetched[$i]['level'];

         $f['parent'] = NULL;
         $f['path']   = array();
         $f['childs'] = array();

         if($f['level'] > $level)
         {
            $level = $f['level'];
         } else
         {
            $level = $f['level'];
         }

         if($level > 1)
         {
            $node = end($chain[$level-1]);
            $f['parent'] = $node['id'];

            $p = $level;
            # BUILD PATH ARRAY
            while(($p--) >1)
            {
               $node = end($chain[$level-$p]);
               if($node)
               {
                  $f['path'][$node['id']] = $node;
               }
            }
            $f['path'] = array_reverse($f['path'], TRUE);
         }

         $chain[$level][$f['id']] = $f;
         $chain[$level+1] = &$chain[$level][$f['id']]['childs'];
      }

      self::$prebuildedTree = self::prebuildFlatTree($tree);
   }

   static private function prebuildFlatTree($tree, $flattree = array())
   {
      if(!empty($tree))
      {
         foreach($tree AS $key=>$node)
         {
            $flattree[$key] = $node;
            $flattree = self::prebuildFlatTree($node['childs'], $flattree);
         }
      }
      return $flattree;
   }
}